package com.data_structure_algorithm.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class cardinalitySort {

    public static void main(String[] args) {
    /*    int[] arr = {53, 3, 542, 748, 14, 214};
        sort(arr);

        System.out.println(Arrays.toString(arr));*/
        int[] arrs = new int[100000];
        for (int i = 0; i <100000; i++) {
            arrs[i] = (int) (Math.random() * 80000000);
        }
        String dateStart = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss").format(new Date());
        System.out.println(dateStart);
        sort(arrs);
        String dateEnd = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss").format(new Date());

        System.out.println(dateEnd);

    }

    private static void sort(int[] arr) {
        int count = 0;

        //计算最高位
        int maxIntValue = getMaxIntValue(arr);

        int length = (maxIntValue + "").length();


        //创建0-9  10个桶，每个桶的大小是多少呢？不好确定，定义为arr.length
        int[][] bucket = new int[10][0];


        //创建每个桶对应的下标，由于出桶的时候需要计算下一个索引
        //如bucketIndex[0]代表0个桶的下标，没放入一个数据，++一次，拿出一个数据，--一次  .....
        int[] bucketIndex = new int[10];//该数组中的每个数都对应一个桶，该数组的数量 == 桶的数量

        int flag = 1;

        //控制总体循环数，依据-->最大位数
        for (int i = 0; i < length; i++) {

            //每次循环--> 将原数组中的数据根据位数存入不同的桶
            for (int j = 0; j < arr.length; j++) {

                int bit = arr[j] / flag % 10;

                //将该数据放入对应桶中
                //动态扩容
                bucket[bit] = arrayAppend(bucket[bit]);
                bucket[bit][bucketIndex[bit]++] = arr[j];
                //bucketIndex[bit]++;//默认此以为数组均为0，添加元素后，对应索引++

            }

            //将每个桶中数据放如原数组，该轮结束
            //遍历二维数组（桶）
            int srcIndex = 0; //代表原数组下标

            //循环桶索引，不为0说明该桶有数据
            for (int j = 0; j < bucketIndex.length; j++) {
                //该桶不为0，有数据
                if (bucketIndex[j] != 0) {
                    //遍历该桶
                    for (int k = 0; k < bucketIndex[j]; k++) {
                        arr[srcIndex++] = bucket[j][k];
                       // System.out.println("循环了"+ count++ +"次");
                    }

                }
                bucketIndex[j] = 0;

            }




            //为下次循环做位数运算初始化
            //首次为 arr[j] / flag * 1 % 10;
            //下次为 arr[j] / flag*10 % 10;
            //下次为 arr[j] / flag*100 % 10;
            flag *= 10;
        }

        System.out.println(Arrays.toString(arr));


    }

    public static int getMaxIntValue(int[] arr) {
        int max = arr[0];

        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]) {

                max = arr[i];

            }
        }

        return max;
    }

    //扩容++
    private static int[] arrayAppend(int[] arr) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        //arr[arr.length - 1] = value;
        return arr;
    }


}
